#if !defined(INTERVALS_PER_CONTIG_H)
#define INTERVALS_PER_CONTIG_H


#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
#include <unordered_map>

namespace intervals_per_contig
{
	//!_______________________________________________________________________________________
	//!
	//! 	t_interval
	//! 
	//! 		contains extra id for lookups
	//!     
	//!     \author lg (1/7/2011)
	//!_______________________________________________________________________________________
	struct t_interval
	{
		long                    beg;
		long                    end;
		long                    id;
		t_interval(long beg_, long end_, long id_ = 0): beg(beg_), end(end_), id(id_){}
		std::string					str() const;
	};
	inline bool operator <(const t_interval& me, const t_interval& other)
	{
		if (me.beg == other.beg)
			return me.end < other.end;
		return me.beg < other.beg;
	}








	//!___________________________________________________________________________________
	//!
	//!     t_interval_search_cache
	//!     
	//!     \author lg (1/7/2011)
	//!___________________________________________________________________________________
	class t_intervals;

	// need to change for c++0x
	typedef std::vector<t_interval> 		t_vec_intervals;
	typedef t_vec_intervals::iterator 		i_interval;
	typedef t_vec_intervals::const_iterator ci_interval;
	struct t_interval_search_cache
	{
		static t_vec_intervals 				out_of_bounds_intervals;
		const t_intervals*					pintervals;
		ci_interval							i_next;
		ci_interval							i_prev;
		t_interval_search_cache() : pintervals(0), 
									i_next(out_of_bounds_intervals.begin() + 1),
									i_prev(out_of_bounds_intervals.begin())
		{}
		std::string							str() const;
		bool								single() const {return i_next == i_prev;}
		bool								prev_out_of_bounds() const { return i_prev == out_of_bounds_intervals.begin();}
		bool								next_out_of_bounds() const { return i_next == out_of_bounds_intervals.begin() + 1;}
		void								set_prev_out_of_bounds() { i_prev = out_of_bounds_intervals.begin();}
		void								set_next_out_of_bounds() { i_next = out_of_bounds_intervals.begin() + 1;}
        void                                operator++();
        void                                operator++(int) {operator++();}
        bool                                contains(long test_pos, long& dist, ci_interval& closest_interval) const;
        bool                                contains(long test_pos) const;

	};

	//!___________________________________________________________________________________
	//!
	//!     t_intervals
	//! 
	//! 		algorithms assume
	//!  			non-overlapping intervals
	//!  			open-closed coordinates
	//!     
	//!     \author lg (1/7/2011)
	//!___________________________________________________________________________________
	class t_intervals
	{

	public:
		// 

		t_vec_intervals		data;
		bool				unsorted;

		t_intervals& 	bracket_by(long by, bool do_not_combine_afterwards = false);
		t_intervals& 	combine_with(const t_intervals& other);
		t_intervals& 	combine_close_neighbours(long min_distance);
		t_intervals& 	combine_overlapping () {return combine_close_neighbours(0);}
		t_intervals& 	complement(long first, long last);
		t_intervals& 	expand_by(long by, bool do_not_combine_afterwards = false);
		t_intervals& 	intersect_with(t_intervals& other );
		t_intervals&	touch(t_intervals& other );

		t_intervals& 	remove_intervals_smaller_than(long min_length);
		t_intervals& 	subtract(t_intervals& other );
   
		// Some functions not const because they avoid an additional copy of the data
		//  	and therefore require combine_close_neighbours()
		//  	1. complemented
		//  	2. intersected_with
		//  	3. subtracted
		// 
		t_intervals  	bracketed_by(long by, bool do_not_combine_afterwards = false) 	const;
		t_intervals  	combined_with(const t_intervals& other) 						const;
		t_intervals  	overlapping_combined() 											const
							{t_intervals ret(*this); ret.combine_overlapping(); return ret;}
		t_intervals  	close_neighbours_combined(long min_distance) 					const;
		t_intervals  	complemented(long first, long last);
		t_intervals  	expanded_by(long by, bool do_not_combine_afterwards = false) 	const;
		t_intervals  	intersected_with(t_intervals& other );
		t_intervals		touched_by(t_intervals& other ) 								const;
		t_intervals  	removed_intervals_smaller_than(long min_length) 				const;
		t_intervals  	subtracted(t_intervals& other );

		long  					len() const ;
		t_vec_intervals::size_type  	size() const { return data.size(); }


		// tests take a t_interval_search_cache for speed
		bool 				contains(long test_pos, t_interval_search_cache& cache_for_search) const;
        bool 				contains(long test_pos) const
                            {
                                t_interval_search_cache interval_pair;
                                return contains(test_pos);
                            }
		bool				any_closest(long test_pos, long& dist, ci_interval& closest_interval, t_interval_search_cache& cache_for_search) const;
        bool                any_closest(long test_pos, long& dist, ci_interval& closest_interval) const 
                            {
                                    t_interval_search_cache interval_pair;
                                    return any_closest(test_pos, dist, closest_interval);
                            }
		void				swap(t_intervals& other){other.data.swap(data); std::swap(unsorted, other.unsorted);}
		t_intervals& operator=(const t_intervals& other){data = other.data; unsorted = other.unsorted; return *this;}
		t_intervals():unsorted(true){}
		t_intervals(const t_intervals& other): data(other.data), unsorted(other.unsorted){}
		~t_intervals()		{}
		void				sort();
	private:
		void				get_flanking_intervals(long test_pos, t_interval_search_cache& cache_for_search) const;

	};


	
	//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
	// 
	//     t_intervals_per_contig

	//		Non-overlapping intervals	
	// 		Uses open closed coordinates
	// 
	//8888888888888888888888888888888888888888888888888888888888888888888888888888888888888888
	typedef std::unordered_map<std::string, t_intervals > 	t_map_str_intervals;
	typedef t_map_str_intervals::iterator 					i_map_str_intervals;
	typedef t_map_str_intervals::const_iterator 			ci_map_str_intervals;

	//!_______________________________________________________________________________________
	//!
	//! 	t_intervals_per_contig
	//! 
	//!     
	//!     \author lg (1/7/2011)
	//!_______________________________________________________________________________________
	struct t_intervals_per_contig
	{
		t_intervals_per_contig& 	bracket_by(long by, bool do_not_combine_afterwards = false);
		t_intervals_per_contig& 	combine_with(const t_intervals_per_contig& other);
		t_intervals_per_contig& 	combine_close_neighbours(long min_distance);
		t_intervals_per_contig& 	combine_overlapping () {return combine_close_neighbours(0);}
		t_intervals_per_contig& 	complement(long first, long last);
		t_intervals_per_contig& 	expand_by(long by, bool do_not_combine_afterwards = false);
		t_intervals_per_contig& 	intersect_with(t_intervals_per_contig& other );
		t_intervals_per_contig&		touch(t_intervals_per_contig& other );
		t_intervals_per_contig& 	remove_intervals_smaller_than(long min_length);
		t_intervals_per_contig& 	subtract(t_intervals_per_contig& other );

		t_intervals_per_contig  	bracketed_by(long by, bool do_not_combine_afterwards = false)  	const;
		t_intervals_per_contig  	combined_with(const t_intervals_per_contig& other) 				const;
		t_intervals_per_contig  	overlapping_combined() {t_intervals_per_contig ret(*this); ret.combine_overlapping(); return ret;}
		t_intervals_per_contig  	close_neighbours_combined(long min_distance) 					const;
		t_intervals_per_contig  	complemented(long first, long last);
		t_intervals_per_contig  	expanded_by(long by, bool do_not_combine_afterwards = false) 	const;
		t_intervals_per_contig  	intersected_with(t_intervals_per_contig& other );
		t_intervals_per_contig  	touched_by(t_intervals_per_contig& other ) 						const;
		t_intervals_per_contig  	removed_intervals_smaller_than(long min_length) 				const;
		t_intervals_per_contig  	subtracted(t_intervals_per_contig& other );

		//	total (cummulative) length of intervals
		long                   len() const ;
		//	total (cummulative) number of intervals
		t_vec_intervals::size_type	size() const;
		void						clear() {data.clear();}
		void						sort();


		// tests take a t_interval_search_cache for speed
		bool 						contains(const std::string& contig, long test_pos, t_interval_search_cache& cache_for_search) const;
		bool 						contains(const std::string& contig, long test_pos) const
									{
										t_interval_search_cache cache_for_search;
										return contains(contig, test_pos, cache_for_search);
									}

		bool						any_closest(const std::string& contig, long test_pos, long& dist, ci_interval& closest_interval, t_interval_search_cache& cache_for_search) const;
		bool                		any_closest(const std::string& contig, long test_pos, long& dist, ci_interval& closest_interval) const
									{
										t_interval_search_cache cache_for_search;
										return any_closest(contig, test_pos, dist, closest_interval, cache_for_search);
									}
		t_intervals_per_contig& operator=(const t_intervals_per_contig& other){data = other.data;return *this;}
		t_intervals_per_contig(const t_intervals_per_contig& other):data(other.data){}
		t_intervals_per_contig(){}
		~t_intervals_per_contig(){}
										
		t_map_str_intervals			data;

		// get sorted contig names
		enum eSORT_CONTIGS{eSORT_BY_CANONICAL_CHROMOSOMES, eSORT_BY_EMBEDDED_NUMBERS, eSTD_SORT};
		std::vector<std::string> 	get_sorted_contigs(eSORT_CONTIGS sort_mode = eSORT_BY_CANONICAL_CHROMOSOMES) const;

	};


	// 
	// read and write
	// 
	void write_intervals(	std::ostream& 					f_intervals, 
							const t_intervals_per_contig& 	intervals, 
							const std::string&				interval_type_name,
							bool 							zero_based_coordinates = false,
							bool							ignore_type_name = false
							);
	inline void write_intervals(	std::ostream& 					f_intervals, 
									const t_intervals_per_contig& 	intervals, 
									bool 							zero_based_coordinates = false
							)
	{	write_intervals(f_intervals, intervals, std::string(), zero_based_coordinates, true);}

	enum eINTERVAL_FILE_FORMAT{eRAW_FORMAT, eGFF_FORMAT};
	void read_intervals(std::istream& f_intervals, t_intervals_per_contig& intervals_by_contig, 
						bool zero_based_coordinates = false, eINTERVAL_FILE_FORMAT file_format = eRAW_FORMAT, 
						bool throw_exception_on_error = true,
						std::ostream* error_strm = 0);
	void read_named_intervals(std::istream& f_intervals, t_intervals_per_contig& intervals_by_contig, 
							std::vector<std::string>& interval_names, bool zero_based_coordinates =false);



	/*
	typedef std::vector<t_intervals_per_contig> t_vec_intervals_per_contig;
	 
	typedef t_vec_intervals_per_contig::iterator 	i_vec_intervals_per_contig;

	void write_intervals_by_type(	std::ostream& 						f_intervals, 
									std::map<std::string, unsigned>&	map_interval_type_to_index, 
									std::vector<std::string> 			interval_type_names, 
									t_vec_intervals_per_contig& 			intervals_by_contig_by_type,
									bool 							zero_based_coordinates = false);
	void read_intervals_by_type(std::istream& 						f_intervals, 
								t_vec_intervals_per_contig& 			intervals_by_contig_by_type, 
								std::map<string, unsigned>& 		map_interval_type_to_index, 
								std::vector<std::string>& 			additional_interval_types, 
								bool 							zero_based_coordinates = false);

	//
	//  use of map deprecated
	// 
	typedef std::unordered_map<std::string, t_intervals_per_contig> 	t_intervals_per_contig_by_type;
	typedef t_intervals_per_contig_by_type::iterator 	i_intervals_per_contig_by_type;
	//void read_intervals_by_type(t_intervals_per_contig_by_type& intervals_by_contig_by_type, std::istream& f_intervals, 
									bool 							zero_based_coordinates = false);
	*/

}

#endif	// INTERVALS_PER_CONTIG_H
